import java.util.concurrent.*;

/**
 * Created by L.jp
 * Description:    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 *     每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * User: 86189
 * Date: 2023-03-17
 * Time: 11:06
 */
public class Solution {
    public static int climbStairs(int n) {
        //斐波那契变种，第一个数不是0,是1，第二个数是2，需要另外处理，后面的数按照斐波那契的规律就行
      /*  if(n==1 || n==2){
            return n;
        }
        int a1=1;
        int a2=2;
        int a3=-1;
        while ( n>2 ){
            a3=a1+a2;
            a1=a2;
            a2=a3;
            n--;
        }
        return a2;*/
        //递归解决，但是会超出时间限制
       /* if(n==1 || n==2){
            return n;
        }
        return climbStairs( n-1 )+climbStairs( n-2 );*/
        
        //动态规划
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        //借助第0个位置(其实是没有的，都是为了后期的状态)，题目中真实的环境是从第一个位置和第二位置开始的
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
    
    public static void main (String[] args) {
        System.out.println( climbStairs( 4 ) );
    }
}
